package com.ting.test.algorithms.单调栈;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * 给定一个只包含正数的，没有重复值的数组arr，找出数组中每一个元素的左边和右边离他最近的比他小的值
 */
public class 单调栈定义例题1 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 2, 6, 1, 7, 0};
        int[][] result = process(arr);
    }

    private static int[][] process(int[] arr) {
        if (arr == null) {
            return null;
        }

        int[][] result = new int[arr.length][2];
        if (arr.length == 1) {
            result[0][0] = -1;
            result[0][1] = -1;
            return result;
        }

        Stack<Integer> stack = new Stack<Integer>();// 注意 栈中存储的是元素的下标
        stack.push(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            while (!stack.isEmpty() && stack.peek() > arr[i]) {
                int pop = stack.pop();
                result[pop][1] = arr[i];
                if (!stack.isEmpty()) {
                    result[pop][0] = stack.peek();
                } else {
                    // 如果前面没元素了，表明左边没有比他小的了 返回-1
                    result[pop][0] = -1;
                }
            }
            stack.push(i);
        }

        // 还需要考虑一种情况 拿就是 有可能数组遍历完了，栈中还有元素
        //极端情况下，如果数组元素正好是一个单调递增的，那么可能所有的元素都还在里面

        while (!stack.isEmpty()) {
            int pop = stack.pop();
            result[pop][1] = -1;//此时栈中的元素的右边都没有比他小的了
            if (!stack.isEmpty()) {
                result[pop][0] = stack.peek();
            } else {
                // 如果前面没元素了，表明左边没有比他小的了 返回-1
                result[pop][0] = -1;
            }
        }

        return result;
    }

    private static int[][] process2(int[] arr) {
        if (arr == null) {
            return null;
        }

        int[][] result = new int[arr.length][2];
        if (arr.length == 1) {
            result[0][0] = -1;
            result[0][1] = -1;
            return result;
        }

        Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>();
        stack.push((ArrayList<Integer>) Arrays.asList(arr[0]));
        for (int i = 1; i < arr.length; i++) {
            while (!stack.isEmpty() && stack.peek().get(0) >= arr[i]) {

                ArrayList<Integer> pop = stack.pop();//如果要弹出就是整个列表弹出
                if (pop.get(0) == arr[i]) {//如果是等于则把该元素加入列表，重写入栈
                    pop.add(i);
                    stack.push(pop);
                    continue;
                }

                //如果是大于 则当前弹出的列表需要全部计算

                for (int index : pop) {
                    result[index][1] = arr[i];
                    if (!stack.isEmpty()) {
                        result[index][0] = stack.peek().get(stack.peek().size()-1);//取最后一个元素
                    } else {
                        // 如果前面没元素了，表明左边没有比他小的了 返回-1
                        result[index][0] = -1;
                    }
                }

            }
            stack.push((ArrayList<Integer>) Arrays.asList(arr[i]));
        }

        // 还需要考虑一种情况 拿就是 有可能数组遍历完了，栈中还有元素
        //极端情况下，如果数组元素正好是一个单调递增的，那么可能所有的元素都还在里面

        while (!stack.isEmpty()) {
            ArrayList<Integer> pop = stack.pop();//如果要弹出就是整个列表弹出
            //如果是大于 则当前弹出的列表需要全部计算

            for (int index : pop) {
                result[index][1] =-1;//此时栈中的元素的右边都没有比他小的了
                if (!stack.isEmpty()) {
                    result[index][0] = stack.peek().get(stack.peek().size()-1);//取最后一个元素
                } else {
                    // 如果前面没元素了，表明左边没有比他小的了 返回-1
                    result[index][0] = -1;
                }
            }
        }
        return result;
    }

}
